package daily_exercise;

import model.ListNode;

import java.math.BigInteger;
import java.util.*;

public class Demo8 {


    // 729. 我的日程安排表 I
    class MyCalendar {

        private TreeSet<int[]> calendar;

        public MyCalendar() {
            calendar = new TreeSet<>((a, b) -> a[0] - b[0]);
        }

        public boolean book(int startTime, int endTime) {
            int[] elem = new int[]{startTime, endTime};
            int[] left = calendar.floor(elem);
            if (left != null && left[1] > startTime) return false;
            int[] right = calendar.ceiling(elem);
            if (right != null && right[0] < endTime) return false;

            calendar.add(elem);
            return true;
        }
    }



    // 3280. 将日期转换为二进制表示
    public String convertDateToBinary(String date) {
        String[] strs = date.split("-");
        StringBuilder res = new StringBuilder();
        for (String s : strs) {
            res.append(convert(Integer.parseInt(s)));
            res.append('-');
        }
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }
    private String convert(int num) {
        StringBuilder res = new StringBuilder();
        while (num > 0) {
            res.append(num % 2);
            num /= 2;
        }
        return res.reverse().toString();
    }




    // 3065. 超过阈值的最少操作数 I
    public int minOperations(int[] nums, int k) {
        int res = 0;
        for (int x : nums) {
            if (x < k) {
                res++;
            }
        }
        return res;
    }



    // 3066. 超过阈值的最少操作数 II
    public int minOperations2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int flag = Integer.MAX_VALUE;
        for (int x : nums) {
            if (x < k) {
                pq.add(x);
            } else {
                flag = Math.min(flag, x);
            }
        }

        int res = 0;
        while (!pq.isEmpty()) {
            int num1 = pq.poll();
            int num2 = pq.isEmpty() ? flag : pq.poll();
            long tmp = (long)Math.min(num1, num2) * 2 + Math.max(num1, num2);
            if (tmp < k) {
                pq.add((int)tmp);
            }
            res++;
        }
        return res;
    }



    // 2270. 分割数组的方案数
    public int waysToSplitArray(int[] nums) {
        long sum = 0;
        for (int x : nums) {
            sum += x;
        }

        int res = 0, n = nums.length;
        long prevSum = 0;
        for (int i = 0; i < n - 1; i++) {
            prevSum += nums[i];
            if (prevSum >= sum - prevSum) res++;
        }
        return res;
    }



    // 2275. 按位与结果大于零的最长组合
    public int largestCombination(int[] candidates) {
        // 统计某个比特位为1,且最多有多少个数该比特位为1
        int[] hash = new int[32];
        for (int i = 0; i < 32; i++) {
            for (int x : candidates) {
                if ((1<<i & x) > 0) {
                    hash[i]++;
                }
            }
        }

        int res = 1;
        for (int i = 0; i < 32; i++) {
            res = Math.max(res, hash[i]);
        }
        return res;
    }



    // 3270. 求出数字答案
    public int generateKey(int num1, int num2, int num3) {
        StringBuilder res = new StringBuilder();
        int count = 3;  // 记录当前大于 0 的数字个数
        for (int i = 0; i < 4 && count > 0; i++) {
            int min = num1 % 10;
            min = Math.min(min, Math.min(num2 % 10, num3 % 10));
            res.append(min);

            if (num1 > 0 && (num1 /= 10) == 0) count--;
            if (num2 > 0 && (num2 /= 10) == 0) count--;
            if (num3 > 0 && (num3 /= 10) == 0) count--;
        }
        return Integer.parseInt(res.reverse().toString());
    }




    // 3298. 统计重新排列后包含另一个字符串的子字符串数目 II
    public long validSubstringCount2(String word1, String word2) {
        int[] hash = new int[26];
        for (char ch : word2.toCharArray()) {
            hash[ch - 'a']++;
        }

        // 滑动窗口
        int left = 0, right = 0;
        int len1 = word1.length(), len2 = word2.length();
        int count = 0;                  // 统计窗口中包含 word2 的字符数
        int[] tmpHash = new int[26];    // 统计各个字母出现的次数
        long res = 0;
        while (right < len1) {
            char ch = word1.charAt(right);
            // 入窗口
            tmpHash[ch - 'a']++;
            if (hash[ch - 'a'] > 0 && tmpHash[ch - 'a'] <= hash[ch - 'a']) {
                count++;
            }
            // 出窗口
            while (count == len2) {
                res += (long)(len1 - right);
                ch = word1.charAt(left++);
                tmpHash[ch - 'a']--;
                if (hash[ch - 'a'] > 0 && tmpHash[ch - 'a'] < hash[ch - 'a']) {
                    count--;
                }
            }
            right++;
        }
        return res;
    }



    // 3297. 统计重新排列后包含另一个字符串的子字符串数目 I
    public long validSubstringCount(String word1, String word2) {
        int[] hash = new int[26];
        for (char ch : word2.toCharArray()) {
            hash[ch - 'a']++;
        }

        // 滑动窗口
        int left = 0, right = 0;
        int len1 = word1.length(), len2 = word2.length();
        int count = 0;                  // 统计窗口中包含 word2 的字符数
        int[] tmpHash = new int[26];    // 统计各个字母出现的次数
        long res = 0;
        while (right < len1) {
            char ch = word1.charAt(right);
            // 入窗口
            tmpHash[ch - 'a']++;
            if (hash[ch - 'a'] > 0 && tmpHash[ch - 'a'] <= hash[ch - 'a']) {
                count++;
            }
            // 出窗口
            while (count == len2) {
                res += (long)(len1 - right);
                ch = word1.charAt(left++);
                tmpHash[ch - 'a']--;
                if (hash[ch - 'a'] > 0 && tmpHash[ch - 'a'] < hash[ch - 'a']) {
                    count--;
                }
            }
            right++;
        }
        return res;
    }



    // 2264. 字符串中最大的 3 位相同数字
    public String largestGoodInteger(String num) {
        int index = -1;    // 该优质整数单个位数的最大值(0 ~ 9)
        String[] strs = {"000", "111", "222", "333", "444", "555", "666", "777", "888", "999"};
        for (int i = 0, n = num.length(); i < n - 2; i++) {
            if (num.charAt(i) == num.charAt(i + 1) && num.charAt(i + 2) == num.charAt(i + 1)) {
                index = Math.max(index, num.charAt(i) - '0');
            }
        }

        if (index == -1) return "";
        return strs[index];
    }



    // 3019. 按键变更的次数
    public int countKeyChanges(String s) {
        int res = 0;
        char prev = ' ';
        for (char ch : s.toCharArray()) {
            if (prev != ' ' && !(ch == prev || ch == (char)(prev + 32) || ch == (char)(prev - 32))) {
                res++;
            }
            prev = ch;
        }
        return res;
    }



    // 2274. 不含特殊楼层的最大连续楼层数
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int n = special.length;
        int res = special[0] - bottom;
        if (n > 1) {
            res = Math.max(res, top - special[n - 1]);
        } else {
            res = Math.max(res, top - special[0]);
        }

        for (int i = 0; i < n - 1; i++) {
            res = Math.max(res, special[i + 1] - special[i] - 1);
        }
        return res;
    }




    // 3095. 或值至少 K 的最短子数组 I
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        // 滑动窗口
        int[] count = new int[32];
        int left = 0, right = 0;
        int res = 0x3f3f3f3f;
        while (right < n) {
            int x = nums[right];
            if (x >= k) return 1;

            for (int i = 0; i < 32; i++) {
                if ((1<<i & x) > 0) {
                    ++count[i];
                }
            }

            while (calc(count) >= k) {
                res = Math.min(res, right - left + 1);
                x = nums[left++];
                for (int i = 0; i < 32; i++) {
                    if ((1<<i & x) > 0) {
                        --count[i];
                    }
                }
            }
            right++;
        }
        return res == 0x3f3f3f3f ? -1 : res;
    }
    private int calc(int[] count) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (count[i] > 0) {
                res |= (1<<i);
            }
        }
        return res;
    }



    // 2239. 找到最接近 0 的数字
    public int findClosestNumber(int[] nums) {
        int res = -0x3f3f3f3f;
        int target = 0x3f3f3f3f;
        for (int x : nums) {
            if (x == 0) {
                return 0;
            } else {
                if (Math.abs(x) > target) {
                    continue;
                }
                if (Math.abs(x) == target) {
                    res = Math.max(res, x);
                } else {
                    res = x;
                }
                target = Math.abs(x);
            }
        }
        return res;
    }



    // 91. 解码方法
    public int numDecodings(String s) {
        int n = s.length();
        char[] arr = (" " + s).toCharArray();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = arr[1] != '0' ? 1 : 0;

        for (int i = 2; i <= n; i++) {
            if (arr[i] != '0') {
                dp[i] = dp[i - 1];
            }
            int num = (arr[i - 1] - '0') * 10 + (arr[i] - '0');
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }



    // 1561. 你可以获得的最大硬币数目
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int res = 0;
        int n = piles.length / 3;
        for (int i = piles.length - 2; n > 0; i -= 2, n--) {
            res += piles[i];
        }
        return res;
    }




    // 598. 区间加法 II
    public int maxCount(int m, int n, int[][] ops) {
        int x = m, y = n;
        for (int[] arr : ops) {
            x = Math.min(x, arr[0]);
            y = Math.min(y, arr[1]);
        }
        return x * y;
    }


    // 680. 验证回文串 II
    public boolean validPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left++;
            right--;
        }
        if (left > right) return true;
        // 有两种可能
        // 1) 舍弃左边的字符
        int tmpLeft = left + 1, tmpRight = right;
        if (check(s, tmpLeft, tmpRight)) return true;
        // 2) 舍弃右边的字符
        right--;
        return check(s, left, right);
    }
    private boolean check(String s, int left, int right) {
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }



    // 125. 验证回文串
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        char[] arr = s.toUpperCase().toCharArray();
        while (left <= right) {
            while (left <= right && !isRequireChar(arr[left])) {
                left++;
            }
            while (left <= right && !isRequireChar(arr[right])) {
                right--;
            }
            if (left <= right && arr[left] != arr[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    private boolean isRequireChar(char ch) {
        return (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
    }




    // 905. 按奇偶排序数组
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length;
        // 0 ~ left 之间的整数都是偶数， right ~ n - 1之间的整数都是奇数
        int right = n, cur = 0;
        while (cur < right) {
            if (nums[cur] % 2 == 0) {
                cur++;
            } else {
                swap(nums, cur, --right);
            }
        }
        return nums;
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }



    // 922. 按奇偶排序数组 II
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int even = 0, odd = 1;
        while (odd < n) {
            while (even < n - 1 && nums[even] % 2 == 0) {
                even += 2;
            }
            while (odd < n && nums[odd] % 2 == 1) {
                odd += 2;
            }
            if (odd > n) {
                break;
            }
            int tmp = nums[even];
            nums[even] = nums[odd];
            nums[odd] = tmp;
        }
        return nums;
    }



    // 47. 全排列 II
    private List<Integer> path;
    private List<List<Integer>> res;
    private boolean[] vis;
    private int n;
    public List<List<Integer>> permuteUnique(int[] nums) {
        path = new ArrayList<>();
        res = new ArrayList<>();
        n = nums.length;
        vis = new boolean[n];
        Arrays.sort(nums);
        dfs(nums);
        return res;
    }
    private void dfs(int[] nums) {
        if (path.size() == n) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!vis[i] && (i == 0 || (nums[i] != nums[i - 1] || vis[i - 1]))) {
                path.add(nums[i]);
                vis[i] = true;
                dfs(nums);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }



    // 90. 子集 II
//    private List<Integer> path;
//    private List<List<Integer>> res;
//    private int n;
//    private boolean[] vis;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        path = new ArrayList<>();
        res = new ArrayList<>();
        n = nums.length;
        vis = new boolean[n];
        Arrays.sort(nums);
        dfs(nums, 0);
        return res;
    }
    private void dfs(int[] nums, int cur) {
        res.add(new ArrayList<>(path));

        for (int i = cur; i < n; i++) {
            if (!vis[i] && (i == 0 || (nums[i] != nums[i - 1] || vis[i - 1]))) {
                path.add(nums[i]);
                vis[i] = true;
                dfs(nums, i);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }




    // 59. 螺旋矩阵 II
    private int count;
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        count = 1;
        for (int i = 0; i <= n / 2; i++) {
            fillNumber(res, i, n);
        }
        return res;
    }
    private void fillNumber(int[][] nums, int cur, int n) {
        // 从左到右
        for (int j = cur; j <= n - cur - 1; j++) {
            nums[cur][j] = count++;
        }
        // 从上到下
        for (int i = cur + 1; i <= n - cur - 1; i++) {
            nums[i][n - cur - 1] = count++;
        }
        // 从右到左
        for (int j = n - cur - 2; j >= cur; j--) {
            nums[n - cur - 1][j] = count++;
        }
        // 从下到上
        for (int i = n - cur - 2; i > cur; i--) {
            nums[i][cur] = count++;
        }
    }
    
    
    
    // 63. 不同路径 II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[][] dp = new int[n + 1][m + 1];
        dp[0][1] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (obstacleGrid[i - 1][j - 1] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[n][m];
    }



    // 80. 删除有序数组中的重复项 II
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        // 0 ~ left 为已经修改完的数组
        int cur = 0, left = -1;
        while (cur < n) {
            int tmp = cur;
            while (cur < n && nums[cur] == nums[tmp]) {
                cur++;
            }
            // 使用插入法将元素往前移动
            int count = Math.min(cur - tmp, 2);
            while  (count-- > 0) {
                nums[++left] = nums[tmp++];
            }
        }
        return left + 1;
    }



    //
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        if (fast == null || fast.next == null) {
            return null;
        }

        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }



    //
    public int search(int[] nums, int target) {
        // 1. 寻找数组最大值的下标
        int left = 0, right = nums.length - 1, mid = 0;
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            if (nums[mid] >= nums[0]) left = mid;
            else right = mid - 1;
        }
        // 2. 判断 target 所在的区间
        if (target >= nums[0]) {
            left = 0;
        } else {
            left++;
            right = nums.length - 1;
        }
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }


    // 1742. 盒子中小球的最大数量
    public int countBalls(int lowLimit, int highLimit) {
        int[] boxes = new int[46];
        for (int i = lowLimit; i <= highLimit; i++) {
            boxes[calc(i)]++;
        }

        int max = 0;
        for (int x : boxes) {
            max = Math.max(x, max);
        }
        return max;
    }
    private int calc(int num) {
        int res = 0;
        while (num > 0) {
            res += num % 10;
            num /= 10;
        }
        return res;
    }




    // 1299. 将每个元素替换为右侧最大元素
    public int[] replaceElements(int[] arr) {
        int max = -1;
        int n = arr.length;
        for (int i = n - 1; i >= 0; i--) {
            int tmp = arr[i];
            arr[i] = max;
            max = Math.max(tmp, max);
        }
        return arr;
    }



    // 2506. 统计相似字符串对的数目
    public int similarPairs(String[] words) {
        int n = words.length;
        boolean[][] flag = new boolean[n][26];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            char[] arr = words[i].toCharArray();
            for(char ch : arr) {
                if (!flag[i][ch - 'a']) {
                    flag[i][ch - 'a'] = true;
                    count[i]++;
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j ++) {
                if (count[i] != count[j]) continue;
                boolean b = true;
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if ((!flag[i][ch - 'a'] && flag[j][ch - 'a']) || (flag[i][ch - 'a'] && !flag[j][ch - 'a'])) {
                        b = false;
                        break;
                    }
                }
                if (b) res++;
            }
        }
        return res;
    }



    // 2595. 奇偶位数
    public int[] evenOddBit(int n) {
        int[] ans = new int[2];
        for (int i = 0; i < 32; i++) {
            if ((n >> i) == 0) break;
            if ((n >> i & 1) == 0) continue;
            if (i % 2 == 0) ans[0]++;
            else ans[1]++;
        }
        return ans;
    }



    // 2353. 设计食物评分系统
    class FoodRatings {
        // 食物到烹饪方式的映射
        Map<String, String> foodToCuisine;
        // 食物到评分的映射
        Map<String, Integer> foodToRating;
        // 烹饪方式到食物评分的 TreeSet 映射
        Map<String, TreeSet<Pair<String, Integer>>> cuisineToFoods;

        public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
            foodToCuisine = new HashMap<>();
            foodToRating = new HashMap<>();
            cuisineToFoods = new HashMap<>();

            for (int i = 0; i < foods.length; i++) {
                String food = foods[i];
                String cuisine = cuisines[i];
                int rating = ratings[i];

                // 维护食物到烹饪方式和评分的映射
                foodToCuisine.put(food, cuisine);
                foodToRating.put(food, rating);

                // 初始化烹饪方式的 TreeSet
                cuisineToFoods.putIfAbsent(cuisine, new TreeSet<>((a, b) -> {
                    if (!a.getValue().equals(b.getValue())) {
                        return b.getValue() - a.getValue(); // 按评分降序
                    } else {
                        return a.getKey().compareTo(b.getKey()); // 按名称字典序升序
                    }
                }));

                // 将食物添加到对应烹饪方式的 TreeSet 中
                cuisineToFoods.get(cuisine).add(new Pair<>(food, rating));
            }
        }
        public void changeRating(String food, int newRating) {
            String cuisine = foodToCuisine.get(food);
            int oldRating = foodToRating.get(food);

            // 从 TreeSet 中删除旧评分对应的食物
            cuisineToFoods.get(cuisine).remove(new Pair<>(food, oldRating));

            // 更新评分
            foodToRating.put(food, newRating);

            // 将新评分对应的食物重新插入 TreeSet
            cuisineToFoods.get(cuisine).add(new Pair<>(food, newRating));
        }
        public String highestRated(String cuisine) {
            if (!cuisineToFoods.containsKey(cuisine) || cuisineToFoods.get(cuisine).isEmpty()) {
                return "";
            }
            return cuisineToFoods.get(cuisine).first().getKey();
        }
        // Pair 类
        class Pair<K, V> {
            K key;
            V value;

            public Pair(K key, V value) {
                this.key = key;
                this.value = value;
            }

            public K getKey() {
                return key;
            }

            public V getValue() {
                return value;
            }

            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Pair<?, ?> pair = (Pair<?, ?>) o;
                return Objects.equals(key, pair.key) && Objects.equals(value, pair.value);
            }

            public int hashCode() {
                return Objects.hash(key, value);
            }
        }
    }



    // 132. 分割回文串 II
    public int minCut(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        // 1. 先统计区间 i~j 的字符串是否为回文字符串
        // dp[i][j] = dp[i + 1][j - 1]
        boolean[][] flag = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            flag[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    flag[i][j] = i + 1 == j ? true : flag[i + 1][j - 1];
                }
            }
        }
        // 2. dp[i]: 以 i 为结尾的字符串分割为若干回文子串的最少分割次数
        int[] dp = new int[n];
        Arrays.fill(dp, 0x3f3f3f3f);
        for(int i = 0; i < n; i++) {
            if (flag[0][i]) dp[i] = 0;
            else {
                for(int j = i; j >= 0; j--) {
                    if (flag[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }



    // 131. 分割回文串
//    List<List<String>> res;
//    List<String> path;
//    int n;
//    public List<List<String>> partition(String s) {
//        res = new ArrayList<>();
//        path = new ArrayList<>();
//
//        char[] arr = s.toCharArray();
//        n = arr.length;
//        // 1. 先统计区间 i~j 的字符串是否为回文字符串
//        // dp[i][j] = dp[i + 1][j - 1]
//        boolean[][] dp = new boolean[n][n];
//        for (int i = n - 1; i >= 0; i--) {
//            dp[i][i] = true;
//            for (int j = i + 1; j < n; j++) {
//                if (arr[i] == arr[j]) {
//                    dp[i][j] = i + 1 == j ? true : dp[i + 1][j - 1];
//                }
//            }
//        }
//        // 2. 递归统计所有的可能性
//        dfs(dp, 0, s);
//        return res;
//    }
//    private void dfs(boolean[][] dp, int i, String s) {
//        if (i == n) {
//            res.add(new ArrayList<>(path));
//            return;
//        }
//
//        for (int j = i; j < n; j++) {
//            if (dp[i][j]) {
//                String tmp = s.substring(i, j + 1);
//                path.add(tmp);
//                dfs(dp, j + 1, s);
//                path.remove(path.size() - 1);
//            }
//        }
//    }



    // 1745. 分割回文串 IV
    public boolean checkPartitioning(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        boolean[][] flag = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            flag[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] == arr[i]) {
                    flag[i][j] = i + 1 == j ? true : flag[i + 1][j - 1];
                }
            }
        }

        for (int i = n - 1; i > 1; i--) {
            if (!flag[i][n - 1]) continue;
            // i~n-1 已经为回文字符串
            for (int j = i - 1; j > 0; j--) {
                if (flag[j][i - 1] && flag[0][j - 1]) return true;
            }
        }
        return false;
    }




    // 1328. 破坏回文串
    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n == 1) return "";
        char[] arr = palindrome.toCharArray();
        int i = 0;
        while (i < n) {
            // 1. n 为奇数，处于中间的字符无论怎么替换都是回文串
            if (i == n - i - 1) {
                i++;
                continue;
            }
            // 2. 只有小于 arr[left] 的字符才能被替换
            boolean flag = false;
            for (char ch = 'a'; ch < arr[i]; ch++) {
                arr[i] = ch;
                flag = true;
                break;
            }
            // 已有字符被替换，直接结束循环
            if (flag) break;

            // 3. 前面的字符都不能替换，且 i == n - 1时，直接替换为当前字符后一个字符
            if (i == n - 1) {
                arr[i]++;
                break;
            }
            i++;
        }
        if (i == n) return "";
        return new String(arr);
    }
}
